package cn.edu.njust.alg.leetcode;

/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_207_Course_Schedule {

	public static boolean canFinish(int numCourses, int[][] prerequisites) {
		if (prerequisites == null) {
			return true;
		}

		int[] in = new int[numCourses];
		boolean[] isvisited = new boolean[numCourses];
		int i, j;

		for (i = 0; i < prerequisites.length; i++) {
			in[prerequisites[i][0]]++;
		}
		int count = 0;
		while (true) {
			boolean flag = false;
			for (i = 0; i < numCourses; i++) {
				if (!isvisited[i] && in[i] == 0) {
					isvisited[i] = true;
					flag = true;
					count++;
					for (j = 0; j < prerequisites.length; j++) {
						if (prerequisites[j][1] == i) {
							in[prerequisites[j][0]]--;
						}
					}
				}
			}
			if (!flag) {
				return false;
			}
			if (count == numCourses) {
				return true;
			}
		}
	}

	public static void main(String[] args) {
		int numCourses = 3;
		int[][] prerequisites = { { 0, 1 },{2,1} };
		System.out.println(canFinish(numCourses, prerequisites));
	}

}
